package src.BlueBridge.DeepRecursion;

import java.util.Scanner;

/**
    输入正整数n，对1-n进行排列，使得相邻两个数之和均为素数
    输出时从整数1开始，逆时针排列，同一个环恰好输出一次
    n<=16

    如输入:6
    输出:
    1 4 3 2 5 6
    1 6 5 2 3 4

    生成测试法:
    生成全排列然后一个一个去验证

    dfs:
    一条路走到黑，然后递归回溯
 */

public class _12素数环 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] record = new int[n];
        // 初始化第一个位置为1
        record[0] = 1;
        dfs(n, record, 1);
    }

    public static void dfs(int n, int[] r, int cur) {
        // 排完所有的元素
        if (cur == n && isP(r[0] + r[n - 1])) {// 填到末尾了，还有首尾相加为素数才算成功
            print(r);
            return;
        }
        // 尝试用每个数字填到cur这个位置
        for (int i = 2 ; i <= n ; i++) {
            // r中没有i这个数，且和上一个数之和为素数
            if (check(r, i, cur)) {
                // 试着将i放在cur位置，往前走一步
                r[cur] = i;
                dfs(n, r, cur + 1);
                // 回溯
                r[cur] = 0;
            }
        }
    }

    // 判断是不是素数
    public static boolean isP(int k) {
        for (int i = 2 ; i * i <= k ; i++) {
            if (k % i == 0)
                return false;
        }
        return true;
    }

    // 打印素数环
    public static void print(int[] r) {
        for (int i = 0 ; i < r.length ; i++) {
            System.out.print(r[i] + (i == r.length - 1 ? "" : " "));
        }
        System.out.println();
    }

    // 判断i有没有在r中
    public static boolean check(int[] r, int i, int cur) {
        for (int e : r) {
            if (e == i || !isP(r[cur - 1] + i))
                return false;
        }
        return true;
    }
}
